//package work.rightAnswer;
//
//
//import work.TreeNode;
//
//class Solution_236 {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        //二叉树的最近公共祖先：
//        //1.两个子节点分别在头节点的左右子树中
//        //2.两个子节点全部在头节点一个子树中
//        //3.一个子节点在为头节点，另一个在子树内
//
//        //终止条件
//        if(root==null){
//            return null;
//        }
//
//
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//        //left与right只有三种可能，要么是null，要么是p或q，要么是祖宗节点
//        //分情况讨论：
//        //1.如果root当前节点为p或这q，无论左右子树为什么节点直接返回
//        if(root==p||root==q){
//            return root;
//        }
//
//
//        //2.root为空，左节点为空，那么肯定返回右节点
//        if(left==null){
//            return right;
//        }
//
//        //3,root为空，左节点不为空，右节点为空
//        if(right==null){
//            return left;
//        }
//
//        //根节点不为p，q,左右子树都不为空
//        return root;
//    }
//}